package org.example.Monotone_stack;

import java.util.LinkedList;

public class The_largest_rectangle_in_the_bar_chart {
    public static void main(String[] args) {
        //柱状图中最大的矩形

        //给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
        //求在该柱状图中，能够勾勒出来的矩形的最大面积
        int[] heights = {2,4};
        int i = largestRectangleArea(heights);
        System.out.println(i);
    }
    public static int largestRectangleArea(int[] heights) {
        int result = 0;
        int[] height = new int[heights.length + 2];
        height[0] = 0;
        height[height.length-1] = 0;
        for (int i = 0; i < heights.length; i++) {
            height[i+1] = heights[i];
        }

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(0);
        for (int i = 1; i < height.length; i++) {
            if (height[i] >= height[linkedList.getLast()]){
                linkedList.add(i);
            } else {
                while(height[i] < height[linkedList.getLast()]){
                    Integer mid = linkedList.removeLast();
                    Integer left = linkedList.getLast();
                    Integer right = i;
                    Integer h = height[mid];
                    Integer w = right - left - 1;
                    result = Math.max(result,h * w);
                }
                linkedList.add(i);
            }
        }
        return result;
    }
}
